package org.example.myleet.rosalind.cntq;

import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Solution {

    private static final BigInteger MODULO = BigInteger.valueOf(1000000);

    private static BigInteger qSum = BigInteger.ZERO;
    private static BigInteger totalQuartetCountAB = BigInteger.ZERO;
    private static BigInteger totalQuartetCountCD = BigInteger.ZERO;

    public static void main(String[] args) throws IOException, IllegalAccessException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)))) {
            String line = br.readLine();
            int n = Integer.parseInt(line.trim());
            String newick = br.readLine().trim();
            NewickTreeNode root = NewickTreeUtil.parse(null, newick);
            countAB(root);
            countCD(root, BigInteger.ZERO, 0);
            BigInteger res = totalQuartetCountAB.add(totalQuartetCountCD).mod(MODULO);
            System.out.println(res);
        }
    }

    private static int countAB(NewickTreeNode cur) {
        BigInteger cpQSum = new BigInteger(qSum.toString());
        for (NewickTreeNode child : cur.getChildren()) {
            cur.setChildrenLabelCount(cur.getChildrenLabelCount() + countAB(child));
        }
        if (cur.getValue().length() > 0) {
            cur.setChildrenLabelCount(cur.getChildrenLabelCount() + 1);
        }
        if (1 < cur.getChildren().size()) {
            cur.setqHere(BigInteger.valueOf(cur.getChildren().get(0).getChildrenLabelCount()).multiply(BigInteger.valueOf(cur.getChildren().get(1).getChildrenLabelCount())));
            if (cur.getValue().length() > 0) {
                cur.setqHere(cur.getqHere().add(BigInteger.valueOf(cur.getChildrenLabelCount() - 1)));
            }
            if (2 < cur.getChildren().size()) {
                cur.setqHere(cur.getqHere().add(BigInteger.valueOf(cur.getChildren().get(0).getChildrenLabelCount() + cur.getChildren().get(1).getChildrenLabelCount()).multiply(BigInteger.valueOf(cur.getChildren().get(2).getChildrenLabelCount()))));
            }
        }
        totalQuartetCountAB = totalQuartetCountAB.add(cpQSum.multiply(cur.getqHere())).mod(MODULO);
        qSum = qSum.add(cur.getqHere());
        return cur.getChildrenLabelCount();
    }

    private static void countCD(NewickTreeNode cur, BigInteger a, int b) {
        for (NewickTreeNode child : cur.getChildren()) {
            countCD(child, a.add(cur.getqHere()), b + cur.getChildrenLabelCount() - child.getChildrenLabelCount());
        }
        totalQuartetCountCD = totalQuartetCountCD.add(a.subtract(BigInteger.valueOf((long) b * cur.getChildrenLabelCount())).multiply(cur.getqHere())).mod(MODULO);
    }
}
